package com.gitee.ywj1352.leecode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author wenjie.yang on 2019/10/9.
 */
public class DfsAndBfs { // 无向图
    private int v; // 顶点的个数
    private LinkedList<Integer> adj[]; // 邻接表

    public DfsAndBfs(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) { // 无向图一条边存两次
        adj[s].add(t);
        adj[t].add(s);
    }

    public void bfs(int s, int t) {
        if (s == t) return;
        //记录节点是否被访问过
        boolean[] visited = new boolean[v];
        visited[s] = true;
        //记录 还没有访问的节点-> 每次把该节点的子节点 入队列
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        //来记录访问路径 比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3] = 2
        int[] prev = new int[v];
        for (int i = 0; i < v; ++i) {
            prev[i] = -1;
        }
        while (queue.size() != 0) {
            int w = queue.poll();
            for (int i = 0; i < adj[w].size(); ++i) {
                int q = adj[w].get(i);
                if (!visited[q]) {
                    prev[q] = w;
                    if (q == t) {
                        print(prev, s, t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    private void print(int[] prev, int s, int t) { // 递归打印 s->t 的路径
        if (prev[t] != -1 && t != s) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }


    boolean found = false; // 全局变量或者类成员变量

    @SuppressWarnings("all")
    public void dfs(int s, int t) {
        found = false;
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; ++i) {
            prev[i] = -1;
        }
        recurDfs(s, t, visited, prev);
        print(prev, s, t);
    }

    @SuppressWarnings("all")
    //使用的是栈来完成
    private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
        if (found == true) return;
        visited[w] = true;
        if (w == t) {
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size(); ++i) {
            int q = adj[w].get(i);
            if (!visited[q]) {
                prev[q] = w;
                recurDfs(q, t, visited, prev);
            }
        }
    }

    @SuppressWarnings("all")
    //使用 栈 对象来存储 打印对象
    public void dfs2(int s, int t) {
        found = false;
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; ++i) {
            prev[i] = -1;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(s);
        Integer pop = s;
        while (pop != null) {
            if (found == true) return;
            visited[pop] = true;
            if (pop == t) {
                found = true;
                print(prev, s, t);
                return;
            }
            for (int i = 0; i < adj[pop].size(); ++i) {
                int q = adj[pop].get(i);
                if (!visited[q]) {
                    prev[q] = pop;
                    stack.push(q);
                }
            }
            pop = stack.pop();
        }
    }

    public static void main(String[] args) {
        DfsAndBfs dfsAndBfs = new DfsAndBfs(4);
        dfsAndBfs.addEdge(0, 3);
        dfsAndBfs.addEdge(2, 1);
        dfsAndBfs.addEdge(3, 1);
        dfsAndBfs.bfs(0, 2);
    }


}

